package oxing.util;

import java.util.NoSuchElementException;

public class LinkedList<E> {
	final static class Entry<E> {
		E element;
		Entry<E> prev, next;

		public Entry() {
			this.element = null;
			this.prev = this;
			this.next = this;
		}

		public Entry(Entry<E> prev, E element, Entry<E> next) {
			this.element = element;
			this.prev = prev;
			this.next = next;
		}

	}

	private Entry<E> root = new Entry<E>();
	private int size;

	public E getFirst() {
		if (size > 0)
			return root.next.element;
		return null;
	}

	public E getLast() {
		if (size > 0)
			return root.prev.element;
		return null;
	}

	public E removeFirst() {
		if (size > 0)
			return remove(root.next);
		return null;
	}

	public E removeLast() {
		if (size > 0)
			return remove(root.prev);
		return null;
	}

	public void addFirst(E e) {
		Entry<E> newEntry = new Entry<E>(root, e, root.next);
		newEntry.prev.next = newEntry;
		newEntry.next.prev = newEntry;
		size++;
	}

	public void addLast(E e) {
		Entry<E> newEntry = new Entry<E>(root.prev, e, root);
		newEntry.prev.next = newEntry;
		newEntry.next.prev = newEntry;
		size++;
	}

	private E remove(Entry<E> e) {
		if (e == root)
			throw new NoSuchElementException();
		e.prev.next = e.next;
		e.next.prev = e.prev;
		size--;

		E result = e.element;
		e.next = e.prev = null;
		e.element = null;
		return result;
	}
}
